package com.sakura.二分查找;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;

public class Code06_每一个查询的最大美丽值 {

    public static void main(String[] args) {
        Code06_每一个查询的最大美丽值 code06 = new Code06_每一个查询的最大美丽值();
        int[][] items = {{193, 732}, {781, 962}, {864, 954}, {749, 627}, {136, 746}, {478, 548}, {640, 908}, {210, 799}, {567, 715}, {914, 388}, {487, 853}, {533, 554}, {247, 919}, {958, 150}, {193, 523}, {176, 656}, {395, 469}, {763, 821}, {542, 946}, {701, 676}};
        int[] queries = {885, 1445, 1580, 1309, 205, 1788, 1214, 1404, 572, 1170, 989, 265, 153, 151, 1479, 1180, 875, 276, 1584};
        System.out.println(Arrays.toString(code06.maximumBeauty(items, queries)));
    }

    public int[] maximumBeauty(int[][] items, int[] queries) {
        Arrays.sort(items, Comparator.comparingInt(o -> o[0]));
        // 计算当前位置，以前出现的最大美丽数
        for (int i = 1; i < items.length; i++) {
            items[i][1] = Math.max(items[i][1], items[i - 1][1]);
        }

        int i = 0;
        for (int target : queries) {
            int j = lowerBound(items, target);
            queries[i++] = j > 0 ? items[j][1] : 0;
        }
        return queries;
    }

    private int lowerBound(int[][] items, int target) {
        int left = -1;
        int right = items.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (items[mid][0] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}
